package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

/**
 * n 如果比链表还长的话也考虑进去
 * 本题不存在这种情况
 */

public class Q19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n == 0 || head == null) return head;

        ListNode fakeHead = new ListNode(-23121039);
        fakeHead.next = head;
        ListNode quick = fakeHead;
        ListNode slow = fakeHead;

        for (int i = n; i > 0; i--) {
            // 如果已经到链表末尾n还没到0(也就是说n比链表长度还长),就不操作直接返回
            if (quick == null) return head;
            else quick = quick.next;
        }

        while (quick.next != null) {
            quick = quick.next;
            slow = slow.next;
        }

        // 此时slow节点指向的是待删除的前面一个
        quick = slow.next.next;
        slow.next.next = null;
        slow.next = quick;

        return fakeHead.next;
    }
}
